题目
题解
- 注意点
- 数组无序
- 返回下标
暴力
二重循环
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int> v; for(int i = 0; i < nums.size();++i) for(int j = i+1; j < nums.size();++j) if(nums[i] + nums[j] == target) { v.push_back(i); v.push_back(j); } return v; } };
时间复杂度:O($n^{2}$)
- 空间复杂度 O(1)
双指针
- 排序($nlog(n)$)之后使用双指针($O(n)$)找出所求的值
- 所求的是原数组中的下标,所以排序前复制一份。之后利用找到的值来找到下标
需要注意从原数组找下标时,下标大小和数值重复的问题。
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int> tmp = nums; sort(tmp.begin(),tmp.end()); int i = 0; int j = tmp.size()-1; while(i < j) { if(tmp[i] + tmp[j] > target) --j; else if(tmp[i] + tmp[j] < target) ++i; else break; } bool bi = false; bool bj = false; for(int k = 0; k < nums.size();++k) { if(!bi && nums[k] == tmp[i] ) { i=k; bi = true; continue; } if(!bj && nums[k] == tmp[j]) { j = k; bj = true; continue; } } if(i > j) swap(i,j); return {i,j}; } };
时间复杂度: $O(nlog(n) + n + n) = O(nlog(n))$
- 空间复杂度: $O(n)$
两遍哈希
- 利用map或unordered_map将数组中的值和下标关联在一起。
- 这里会注意到一点,可能数组中的值会重复,导致一个值关联多个下标,而实际代码中的结果会使得最后一个重复值关联相应下标。
- 但是这并不会影响结果。如此考虑,因为结果唯一,所以结果要取重复值,则数组中该结果对应的重复值有且仅有2个,不然不满足结果唯一。
- 所以在查找的时候,用的是原数组进行迭代,所以重复的第一个值要找的就是重复的后一个值,所以上述正好满足我们的要求
利用原数组进行查找 target - nums[i] 是否在map中,map::find为O(log(n)),其基于红黑树。unordered_map::find()为O(1),其基于哈希表
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int,int> m; for(int i =0; i < nums.size();++i) m[nums[i]] = i; for(int i =0; i < nums.size();++i) { if(m.find(target-nums[i]) != m.end() && m[target-nums[i]] != i) return {i,m[target-nums[i]]}; } return {}; } };
- 时间复杂度:map:$O(nlog(n))$、unordered_map:$O(n)$
- 空间复杂度:o(n)
一遍哈希
- 利用map或unordered_map将数组中的值和下标关联在一起。
在这里直接循环原数组,查找map中否有target - nums[i]。没有的话加入map中。
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int,int> m; for(int i =0; i < nums.size();++i) { if(m.find(target-nums[i]) != m.end()) { return {m[target-nums[i]],i}; } else { m[nums[i]] = i; } } return {}; } };
- 时间复杂度:map:$O(nlog(n))$、unordered_map:$O(n)$
- 空间复杂度:o(1)